\documentclass[]{article}
\usepackage{xeCJK}
\usepackage{graphicx}
\usepackage{caption}
\captionsetup{hypcap=true}
\usepackage{color}
\usepackage[colorlinks]{hyperref}
\usepackage{subfigure}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{indentfirst}
\usepackage{bm}
\usepackage{multirow}
\usepackage{tabularx}

\bibliographystyle{plain}
\definecolor{red}{rgb}{1,0,0}

%opening
\title{若干one-pass learning算法的实现与结果对比研究}
\author{任震}

\begin{document}

\maketitle
%done 求证：BSGD属于在线学习，但不是one-pass；pegasos不是在线学习。两者都属于随机梯度下降。（正确，但是为什么？）
%todo 目录、页眉、页脚、承诺书、封面
\begin{abstract}%350
	面对规模较大的数据，离线学习存在时空复杂度高的问题，无法胜任，而在线学习是处理流式数据的一种重要方法，在处理大规模数据的时候，有助于减轻计算压力，但有一些算法仍然存在空间问题，若设备的物理内存小而数据很多，那么某些在线算法也显得不太适用。特别地，one-pass在线学习算法对每个样本只使用一次，在预测完这个样本并更新当前模型之后，它将被丢弃。因此这种算法不仅能够减轻计算压力，也能减少存储空间的使用。近年人们提出了许多one-pass在线学习算法，其中常见的有PA，LOL，CW等等。另外，我们还研究了一些相关算法，如BSGD，Pegasos，严格来说，它们不属于在线学习或者one-pass，不过的确可以通过改变算法的参数，使得他们可以被看作是one-pass，并且也由于他们被\cite{1}引用并给出了一些有价值的实验数据，所以我们也对其进行了研究。

	在这篇文章中，我们通过研究前人的工作，实现了若干种one-pass learning算法，并在多种基准数据集上测试这些算法，最后我们给出比较结果。
\end{abstract}
\section{引言}%900
	作为处理流式数据的重要方法，在线学习有助于减轻计算压力和存储开销，若在线学习算法对每个样例只使用一次，并且不再存储，那么我们说这种算法属于one-pass在线学习算法，即一遍式在线学习算法。为简洁起见，在不出现歧义的情况下，下文中所指的在线学习算法均指one-pass在线学习。
	
	比较有名的在线学习算法是PA(Passive-Aggressive)算法\cite{2}，它通过前一轮对某一个样例预测的正误来修正下一次的预测参数，最终得到一个线性模型。在此基础上，为了能控制下一轮预测的置信度，研究者们提出了CW(Confidence-Weighted)算法\cite{3}，以及它的软间隔版本SCW(Soft Confidence-Weighted)算法\cite{7}。但是，以上这些算法最终的结果都只能是线性模型，对于线性不可分的数据，它们就无能为力了。为解决这个问题，研究者们提出了相当多的算法，但并不都属于one-pass。其中包括BSGD(Budgeted Stochastic Gradient Descent)算法\cite{6}，是一种基于核的在线学习算法(非one-pass)，一定程度上避免了核技术带来的性能问题。后来有研究者提出LOL(Local Online Learning)算法\cite{1}，它是一种one-pass在线学习算法，同时具有一定的能力来处理非线性数据。除上述算法之外，我们还研究了Pegasos(Primal Estimated sub-GrAdient SOlver for SVM)算法\cite{4}\cite{5}，严格地说，它不属于在线学习算法，但却具有在线学习算法的优秀性能，最终的结果也能收敛到离线SVM算法的解。
	
	这篇文章的结构如下：在第\ref{prob}节，我们简要介绍在线二分类问题，文章将主要关注这类问题；在第\ref{pa}\textasciitilde\ref{pegasos}节将分别讨论PA、CW、SCW、LOL、BSGD、Pegasos算法；在第\ref{expe}节，我们阐述实验条件和测试数据集，并给出各算法的实验结果；最后在第\ref{con}节，我们将对实验结果进行归纳总结。
\section{问题设置}\label{prob}%200
	在本篇文章中，我们主要关注one-pass在线二分类问题。one-pass在线二分类问题包含若干轮，在第$t$轮，算法观测一个样本$(\bm{x}_t,y_t)$，基于其特征$\bm{x}_t\in\mathbb{R}^n$作出预测$\hat{y}_t\in\{-1,+1\}$；做出预测之后，结合样本真实的类别$y_t$，可以求一个``即时损失"，它反映预测的错误程度，并可以被用来修正算法预测参数，以期提高预测准确度，随后，该样本被丢弃，且再也不会被观测到。然后算法在下一轮中，会再观察一个新的样本，继续做出预测、计算损失、修正参数并丢弃...如此循环进行。其中one-pass算法的明显特征是一个样本只会被观测一次且不被存储。
\section{PA算法}\label{pa}%650
	朴素的PA(Passive-Aggressive)算法的思想是这样的：在第$t$轮，算法观测一个样本$(\bm{x}_t,y_t)$，之后更新$\bm{\omega}$，使得$\text{sign}(\bm{\omega}\cdot\bm{x}_t)==y_t$。具体来说，通过求解如下带约束的优化问题来迭代更新$\bm{\omega}$:
	\begin{equation}
	\bm{\omega}_{t+1} = \arg\underset{\bm{w}}{\min} \frac{1}{2}|\bm{\omega}-\bm{\omega}_{t}|^2 \quad \text{s.t.} \quad l(\bm{\omega};(\bm{x}_t,y_t))=0
	\label{eq1}
	\end{equation}
	其中$l(\bm{\omega};(\bm{x},y))$是损失函数，在这篇文章中若未特别说明，损失函数均指 hinge-loss 函数，定义如下：
	\begin{equation}		
		l(\bm{\omega};(\bm{x},y)) =
		\begin{cases}
		0 & y(\bm{\omega}\cdot\bm{x})\ge1,\\
		1-y(\bm{\omega}\cdot\bm{x}) & \text{otherwise}
		\end{cases}
		\label{hingeloss}
	\end{equation}
		
	可以发现，当$l_t=l(\bm{\omega}_t;(\bm{x}_t,y_t))=0$，即该轮预测错误时，$\bm{\omega}_{t+1}=\bm{\omega}_t$，无需更新，这被称为是``Passive"；否则，该轮预测错误，$\bm{\omega}_{t+1}$就必须要更新使得当前的预测损失$l_{t+1}$为零，然后下一轮将使用更新后的参数继续预测，这被称为是``Aggressive"。算法的名称``Passive-Aggressive"因此得名。
		
	问题\eqref{eq1}可用拉格朗日乘子法求解，先考虑$l_t>0$的情况，则可构造函数如下：
	\begin{equation}
	L(\bm{\omega},\tau) = \frac{1}{2}\|\bm{\omega}-\bm{\omega}_t\|^2+\tau(1-y_t(\bm{\omega}_{t}\cdot\bm{x}_t))
	\end{equation}
	其中$\tau$是拉格朗日乘子。分别令$\frac{\partial{L}}{\partial{\bm{\omega}}}=0$与$\frac{\partial{L}}{\partial{\tau}}=0$可得：
	\begin{equation}
	\bm{\omega}=\bm{\omega}_t+\tau y_t\bm{x}_t\label{eq4}
	\end{equation}
	\[\tau = \frac{1-y_t(\bm{\omega}_t\cdot\bm{x}_t)}{\|\bm{x}_t\|^2}\]
		
	结合$l_t=0$的情况，有：
	\[\tau = \frac{l_t}{\|\bm{x}_t\|^2}\]
		
	至此，我们已经讨论了朴素的PA算法，可以发现，朴素的PA算法在第t轮若预测错误，则会修正下一轮预测的参数，但这会带来一个问题，如果第t轮的样本是一个噪声样本，那么很可能导致之后的预测参数朝着错误的方向更新。为缓解这一问题，研究者们采用``软间隔"技术，以容许在预测错误的情况下可以不更新预测参数。软间隔的PA算法有两种变体，一种被称为PA-I，把\eqref{eq1}变成如下形式：
	\begin{equation}
	\bm{\omega}_{t+1} = \arg\underset{\bm{w}}{\min} \frac{1}{2}|\bm{\omega}-\bm{\omega}_{t}|^2+C\xi \quad \text{s.t.} \quad l(\bm{\omega};(\bm{x}_t,y_t))\le\xi\ \text{and}\ \xi\ge0
	\label{eq2}
	\end{equation}
	其中，$\xi$是松弛变量，$C$是一个正数，它控制松弛项对整个目标函数的影响。C越大，$\xi$就相对要越小，就会迫使越多的样本满足$l=0$约束。
		
	PA算法的另一种变体，称为PA-II，通过把$\xi$写成平方形式，精简了\eqref{eq2}中的约束，如下：
	\begin{equation}
	\bm{\omega}_{t+1} = \arg\underset{\bm{w}}{\min} \frac{1}{2}|\bm{\omega}-\bm{\omega}_{t}|^2+C\xi^2 \quad \text{s.t.} \quad l(\bm{\omega};(\bm{x}_t,y_t))\le\xi\
	\label{eq3}
	\end{equation}
	分别求解\eqref{eq2}与\eqref{eq3}可得：
	\begin{equation}
	\tau_t = \min\left\{ C ,\frac{l_t}{\|\bm{x}_t\|^2}\right \}\tag{PA-I}\label{eq5}
	\end{equation}
	或
	\begin{equation}
	\tau_t = \frac{l_t}{\|\bm{x}_t\|^2+\frac{1}{2C}} \tag{PA-II}
	\end{equation}
	这两个变体关于$\bm{\omega}$有相同的解，都是\eqref{eq4}
	
	
	实践当中，我们采用\eqref{eq4}与\eqref{eq5}来实现PA算法。
\section{CW算法}\label{cw}%750
	%误差引入的几个来源：1.参数不一定服从高斯分布；2. 求解优化问题时的近似；3. 没有软间隔；
	在PA算法的基础上，研究者们提出CW(Confidence-Weighted)算法，它通过引入额外的参数，结合当前轮的样本及其预测结果，则可以参数化下一轮预测正确的置信度，令该置信度不小于某个阈值，则能够迭代更新该引入的参数。具体来说，算法假定分类器$\bm{\omega}$服从均值为$\bm{\mu}$、协方差矩阵为$\bm{\Sigma}$的多元高斯分布，其中$\bm{\Sigma}$是一个对角矩阵，保证$\bm{\omega}_i$相互独立。那么，算法将通过更新参数$\bm{\mu}$与$\bm{\Sigma}$来间接更新$\bm{\omega}$。
	
	基于上述假设，为分类样例$(\bm{x}_t,y_t)$，首先随机取$\bm{\omega}\sim\mathcal{N}(\bm{\mu}_t,\bm{\Sigma}_t)$，则可以使用$\text{sign}(\bm{\omega}\cdot\bm{x}_t)$作为该样本的预测类别，同时注意到，该样本关于分类器$\bm{\omega}$产生的``间隔"$y_t(\bm{\omega}\cdot\bm{x}_t)$也服从多元高斯分布：
	\[ M\sim\mathcal{N}(y_t(\bm{\mu_t}\cdot\bm{x}_t), \bm{x}_t^\top\bm{\Sigma}_t\bm{x}_t) \]

	我们的目标是，在第t轮，算法能够调整多元高斯分布，使得下一轮使用随机取的$\bm{\omega}$预测正确的概率不低于$\eta$，同时，这次调整应该越小越好。由此可写出一个优化问题：
	\begin{equation}
	\begin{split}
		(\bm{\mu}_{t+1},\bm{\Sigma}_{t+1})=\min D_{KL}( \mathcal{N}(\bm{\mu},\bm{\Sigma}) \| \mathcal{N}(\bm{\mu}_t,\bm{\Sigma}_t) ) \\
		\text{s.t.}\quad P[M\ge0] = P[y_t(\bm{\omega}\cdot\bm{x}_t)\ge0] >= \eta
		\label{eq6}
	\end{split}
	\end{equation}
	其中，$D_{KL}$是``相对熵"或``KL散度"，它可以衡量两个分布的差异，值越小，则说明两个分布越相似。当且仅当相对熵为0时，两个分布相同；同时，从上述方程的限制条件可以看到，该算法当间隔$y(\bm{\omega}\cdot\bm{x})\ge0$即说明分类正确，并不像SVM等其他算法，要求间隔大于等于1。
	
	先考察方程\eqref{eq6}的限制条件，该条件可重写为：
	\begin{equation}
	y_t(\bm{\mu}_t\cdot\bm{x}_t)\ge\phi\sqrt{\bm{x}_t^\top\bm{\Sigma}_t\bm{x}_t}
	\label{eqcwcond}
	\end{equation}
	其中$\phi=\Phi^{-1}(\eta)$，$\Phi(\cdot)$是标准正态分布的分布函数。但是考虑到不等式右侧存在开方项，为计算简便，索性省略掉根号，直接写成：
	\begin{equation}
	y_t(\bm{\mu}_t\cdot\bm{x}_t)\ge\phi(\bm{x}_t^\top\bm{\Sigma}_t\bm{x}_t)
	\end{equation}
	
	然后考虑方程\eqref{eq6}的目标函数，两个高斯分布的相对熵可展开为：
	\begin{align}
		\begin{split}
				&D_{KL}( \mathcal{N}(\bm{\mu},\bm{\Sigma}) \| \mathcal{N}(\bm{\mu}_t,\bm{\Sigma}_t) )=\\ 
				&\frac{1}{2}\left(\log\left( \frac{\det\bm{\Sigma}_t}{\det\bm{\Sigma}} \right)
				+\text{Tr}(\bm{\Sigma}_t^{-1}\bm{\Sigma})
				+(\bm{\mu}_t-\bm{\mu})^\top\bm{\Sigma}_t^{-1}(\bm{\mu}_t-\bm{\mu})
				-d\right)
				\label{eq7}
		\end{split}
	\end{align}
	忽略\eqref{eq7}中的无关常数$d$，我们可以把优化问题\eqref{eq6}重写为：
	\begin{equation}
		\begin{split}
			(\bm{\mu}_{t+1},\bm{\Sigma}_{t+1})=\min\frac{1}{2}\left(\log\left(\frac{\det\bm{\Sigma}_t}{\det\bm{\Sigma}}\right)+\text{Tr}(\bm{\Sigma}_t^{-1}\bm{\Sigma})+(\bm{\mu}_t-\bm{\mu})^\top\bm{\Sigma}_i^{-1}(\bm{\mu}_t-\bm{\mu})\right)\\
			\text{s.t.}\quad y_t(\bm{\mu}_t\cdot\bm{x}_t)\ge\phi(\bm{x}_t^\top\bm{\Sigma}_t\bm{x}_t)
		\end{split}
	\end{equation}

	该问题仍然可以用拉格朗日乘子法求解，最终得到：
	\begin{equation}
		\begin{split}
		\bm{\mu}_{t+1} = \bm{\mu}_t + \alpha y_t\bm{\Sigma}_t\bm{x}_t\\
		\bm{\Sigma}_{t+1}^{-1} = \bm{\Sigma}_t^{-1}\phi\text{diag}(\bm{x}_t)
		\end{split}
	\end{equation}
	其中，$\alpha$是拉格朗日乘子，值为：
	\begin{align}
		\begin{split}
			&M_t = y_t(\bm{\mu}_t\cdot\bm{x}_t)\\
			&V_t = \bm{x}_t^\top\bm{\Sigma}_t\bm{x}_t\\
			&\gamma_t = \frac{-(1+2\phi M_t)+\sqrt{(1+2\phi M_t)^2-8\phi(M_t-\phi V_t)}}{4\phi V_t}\\
			&\alpha = \max(\gamma, 0)
		\end{split}
	\end{align}
		
\section{SCW算法}\label{scw}%670
	通过研究上述CW算法基本思想可以发现，CW算法不能处理线性不可分的数据，那么会导致在\ref{pa}中提到的问题，噪声样本会严重影响分类器的更新方向，导致最终的结果不准确。因此为了使CW算法能够处理线性不可分数据，研究者们扩展了提出了CW算法，提出SCW(Soft Confidence-Weighted)算法，当分类含噪声的数据集时，比朴素的CW算法更加健壮。
	
	算法的思想大致与CW算法一致。下面我们主要叙述与CW算法的不同点。
	
	考虑CW算法优化问题\eqref{eq6}的限制条件，它的等价形式是\eqref{eqcwcond}，该限制是一个``硬指标"，为了能够允许一部分样本可以分类错误，换句话说，可以不满足该条件，我们需要修改这个条件。具体地，即用下述问题替换\eqref{eq6}：
	\begin{equation}
		l(\mathcal{N}(\bm{\mu},\bm{\Sigma});(\bm{x}_t,y_t))=\max\left(0,\phi\sqrt{\bm{x}_t^\top\bm{\Sigma}\bm{x}_t}-y_t(\bm{\mu}\cdot\bm{x}_t)\right)
		\label{eqscw1}
	\end{equation}
	通过简单的验证即可发现\eqref{eq6}或\eqref{eqcwcond}与$l(\mathcal{N}(\bm{\mu},\bm{\Sigma});(\bm{x}_t,y_t))=0$等价。借助这一新的限制条件，CW的优化问题\eqref{eq6}可重写为：
	\begin{equation}
		\begin{split}
			( \bm{\mu}_{t+1},\bm{\Sigma}_{t+1} )=\arg\underset{\bm{\mu},\bm{\Sigma}}{\min}D_{KL}(\mathcal{N}(\bm{\mu},\bm{\Sigma})\|\mathcal{N}(\bm{\mu}_t,\bm{\Sigma}_t)  )\\
			\text{s.t.}\quad l(\mathcal{N}(\bm{\mu},\bm{\Sigma});(\bm{x}_t,y_t))=0, \phi>0
		\end{split}
	\end{equation}
	
	至此，CW的软间隔版本SCW算法就呼之欲出了，仿照PA算法软间隔的两种变体\eqref{eq2}、\eqref{eq3}，可以得到两种SCW算法，也分别称为SCW-I与SCW-II，其中SCW-I如下：
	\begin{equation}
		\begin{split}
			( \bm{\mu}_{t+1},\bm{\Sigma}_{t+1} )=\arg\underset{\bm{\mu},\bm{\Sigma}}{\min}D_{KL}(\mathcal{N}(\bm{\mu},\bm{\Sigma})\|\mathcal{N}(\bm{\mu}_t,\bm{\Sigma}_t))+Cl(\mathcal{N}(\bm{\mu},\bm{\Sigma});(\bm{x}_t,y_t))
		\end{split}
		\tag{SCW-I}\label{SCW-I}
	\end{equation}
	SCW-II如下：
	\begin{equation}
		\begin{split}
			( \bm{\mu}_{t+1},\bm{\Sigma}_{t+1} )=\arg\underset{\bm{\mu},\bm{\Sigma}}{\min}D_{KL}(\mathcal{N}(\bm{\mu},\bm{\Sigma})\|\mathcal{N}(\bm{\mu}_t,\bm{\Sigma}_t))+Cl(\mathcal{N}(\bm{\mu},\bm{\Sigma});(\bm{x}_t,y_t))^2
		\end{split}
		\tag{SCW-II}\label{SCW-II}
	\end{equation}
	注意，简单起见，两种变体都没有引入松弛变量，而是直接把限制条件写到了目标函数中，这与引入松弛变量的做法是等价的。
	
	这两个变体都可以使用拉格朗日乘子法求解，\eqref{SCW-I}的解如下：
	\begin{align}
		\begin{split}
			\bm{\mu}_{t+1} &= \bm{\mu}_t + \alpha_ty_t\bm{\Sigma}_t\bm{x}_t\\
			\bm{\Sigma}_{t+1} &= \bm{\Sigma}_t - \beta_t\bm{\Sigma}_t\bm{x}_t^\top\bm{x}_t\bm{\Sigma}_t
		\end{split}
		\label{eqscwsol}
	\end{align}
	其中，$
	\alpha_t=\min(C,\max(0,\frac{1}{v_t\zeta}(-m_t\psi+\sqrt{m_t^2\frac{\phi^4}{4}+v_t\phi^2\zeta}))),
	\beta_t = \frac{\alpha_t\phi}{\sqrt{u_t}+v_t\alpha_t\phi},
	u_t = \frac{1}{4}(-\alpha_tv_t\phi+\sqrt{\alpha_t^2v_t^2\phi^2+4v_t})^2,
	v_t = \bm{x}_t^\top\bm{\Sigma}_t\bm{x}_t,
	m_t = y_t(\bm{\mu}_t\cdot\bm{x}_t),
	\psi = 1+\frac{\phi^2}{2},
	\zeta = 1+\phi^2$

	\eqref{SCW-II}的解与\eqref{eqscwsol}有相同的形式，但是系数不同：$ 
	\alpha_t = \max(0,\frac{-(2m_tn_t+\phi^2m_tv_t+\gamma_t)}{2(n_t^2+n_tv_t\phi^2)}),
	\beta_t = \frac{\alpha_t\phi}{\sqrt{u_t}+v_t\alpha_t\phi},
	\gamma_t = \phi\sqrt{\phi^2m_t^2v_t^2+4n_tv_t(n_t+v_t\phi^2)},
	n_t = v_t+\frac{1}{2C}$
	
\section{LOL算法}\label{lol}%1200
	在LOL(Local Online Learning)算法被提出以前，大部分算法都属于线性分类器，只能处理线性可分数据或允许存在一些噪声，比如上文提到的PA、CW、SCW算法等等；而其他一些非线性算法对于线性不可分数据的处理方法主要有以下几种：在线核方法、下文将要提及的基于预算的在线模型、使用随机傅里叶特征的核近似映射模型等等。但是这些方法都存在一些问题，比如，由于算法需要保存训练过程中大量的被分类错误的支持向量(SVs)，那么这种算法在处理大规模数据集时可能存在内存溢出的问题；引入核带来的巨大的计算开销；数据独立，不适应算法的数据流等问题。
	
	也有针对非线性数据的离线学习算法，除了使用核方法的算法之外，还包括一些使用局部分类器的算法，比如LLSVM(Local Linear Support Vector Machine)与LDKL(Local Deep Kernel Learning)。它们利用许多局部分类器来对局部数据进行分类，训练完成之后，各个分类器的联合作为最终的分类器，从而使得算法能够应对非线性数据。这是由于数据从全局来看尽管线性不可分，但是在细部，很可能是线性可分的，通过引入若干个局部线性分类器，分别去处理一部分局部数据，那么最终联合起来，也就能处理整个线性不可分的数据集了。这类使用局部分类器的算法最大的优势在于避免了引入核带来的巨大计算开销。

	受刚才提到的离线局部分类器算法的启示并结合PA、在线K均值聚类算法，研究者们提出了LOL算法。大体来说，在训练过程中，算法同时训练$K$个局部线性分类器$\bm{\omega}_i$，$K$是输入的变量，$i=1,\dots,K$；使用在线K均值聚类算法，把$K$个中心点$\bm{P}_i$分散到整个训练集中，从而把数据集划分为K部分$\{\mathcal{D}(\bm{P}_i)\}$，第$i$个局部分类器$\bm{\omega}_i$仅分类第$i$个中心点对应的一部分数据$\mathcal{D}(\bm{P}_i)$；局部分类器$\bm{\omega}_i$，使用PA算法迭代更新。最终训练出来的$K$个线性分类超平面，即作为最终的模型。
	
	下面对LOL算法进行更详细的阐述。首先定义函数：
	\begin{equation}
		f(\bm{x}) = \sum_{i=1}^{K}f_i(\bm{x})\cdot\bm{1}(\bm{x}\in\mathcal{D}(\bm{P}_i))
	\end{equation}
	其中，$\bm{1}(\cdot)$是指示函数，当$\bm{x}\in\mathcal{D}(\bm{P}_i)$时为1，否则为0；$f_i(\bm{x})=\bm{\omega}_i\cdot\bm{x}$。
	
	算法假定每个局部分类器$\bm{\omega}_i$可被分解为一个公共部分$\bm{\omega}$与一个特定部分$\bm{\mu}_i$。公共部分联系了各个局部分类器，避免各分类器毫不相干而造成过拟合，系数$\lambda$来平衡公共部分与各特定部分。至此，关键问题就是如何更新公共部分$\bm{\omega}$与各个局部分类器各自的部分$\bm{\mu}_i$。这可以通过求解如下优化问题来解决：
	\begin{align}
		\begin{split}
			\bm{\omega}_{t+1},\bm{\mu}_{1,t+1},\dots,\bm{\mu}_{k,t+1} = \arg\underset{\bm{\omega},\bm{\mu}_1,\dots,\bm{\mu_k}}{\min} \frac{\lambda}{2}\|\bm{\omega}-\bm{\omega}_t\|^2 + \frac{1}{2}\sum_{i=1}^k\|\bm{\mu}_i-\bm{\mu}_{i,t}\|^2+C\xi \\
			\text{s.t.}\quad l(\bm{\omega},\bm{\mu}_1,\dots,\bm{\mu}_k;(\bm{x}_t,y_t))\le\xi,\xi\ge0
		\end{split}
		\label{eqLOLOBJ}
	\end{align}
	其中，损失函数$l(\cdot)$与hinge-loss略有不同，定义如下：
	\begin{equation}
		l(\bm{\omega},\bm{\mu}_1,\dots,\bm{\mu}_k;(\bm{x}_t,y_t))=
		\begin{cases}
			0 & y_t\cdot f(\bm{x}_t)\ge 1,\\
			1-y_t\cdot f(\bm{x}_t) & \text{otherwise}
		\end{cases}	
	\end{equation}
	
	为求解上述问题，先构造两个变量：
	\begin{equation}
		\hat{\bm{x}}_t=\left[\frac{\bm{x}_t}{\sqrt{\lambda}},\bm{0},\dots,\bm{0},\bm{x}_t,\bm{0},\dots,\bm{0},\right]
		\label{eqLOL1}
	\end{equation} 
	和
	\begin{equation}
		\hat{\bm{\omega}}=\left[\sqrt{\lambda}\bm{\omega},\bm{\mu}_1,\bm{\mu}_2,\dots,\bm{\mu}_i,\dots,\bm{\mu}_k\right]^\top
		\label{eqLOL2}
	\end{equation}
	使用\eqref{eqLOL1}与\eqref{eqLOL2}，可把\eqref{eqLOLOBJ}重写为：
	\begin{equation}
		\begin{split}
			\hat{\bm{\omega}}_{t+1} = \arg\underset{\hat{\bm{\omega}}}{\min}\left( \frac{1}{2}\|\hat{\bm{\omega}}-\hat{\bm{\omega}}_t\|^2+C\xi \right)\\
			s.t.\quad l(\hat{\bm{\omega}};(\hat{\bm{x}}_t,y_t))\le\xi,\xi\ge0
		\end{split}
		\label{lolobj}
	\end{equation}
	这样，\eqref{lolobj}就能用拉格朗日乘子法求解，构造拉格朗日函数如下：
	\begin{equation}
		\mathcal{L}(\hat{\bm{\omega}},\xi,\eta,\gamma) = \arg\underset{\hat{\bm{\omega}}}{\min}\frac{1}{2}\|\hat{\bm{\omega}}-\hat{\bm{\omega}}_t\|^2+C\xi-\eta(l(\hat{\bm{\omega}};(\hat{\bm{x}}_t,y_t))-\xi)-\gamma\cdot\xi
		\label{eqlolLagr}
	\end{equation}
	其中$\eta$、$\gamma$是拉格朗日乘子。分别令$\frac{\partial{\mathcal{L}}}{\partial{\hat{\bm{\omega}}}}=0$与$\frac{\partial{\mathcal{L}}}{\partial{\eta}}=0$可得：
	\begin{equation}
		\begin{split}
			\hat{\bm{\omega}}_{t+1}=\hat{\bm{\omega}}_t+\eta_ty_t\hat{\bm{x}}_t^\top \\
			\eta_t = \min\left\lbrace C,\frac{l(\hat{\bm{\omega}};(\hat{\bm{x}}_t,y_t))}{\|\hat{\bm{x}}_t\|^2} \right\rbrace
		\end{split}
	\end{equation}

	还剩最后一个问题，即如何安排$K$个中心点的问题，这可以通过采用在线K均值聚类的方法，具体来说，使用最初的$K$个样本作为$K$个中心点的初始值，此后每当观测一个新的样本$(\bm{x}_t,y_t)$，就把它归类到最近的中心点$\bm{P}_i$，然后使用如下公式迭代更新该中心点：
	\begin{equation}
		\bm{P}_i = \bm{P}_i + \frac{1}{n_i}(\bm{x}_t-\bm{P}_i)
	\end{equation}
	其中，$n_i$是属于第$i$个中心点的样本个数。
	
\section{BSGD算法}\label{bsgd}%1200
	面对大规模机器学习，计算复杂度是主要的限制因素，目前大规模机器学习已经屡见不鲜，因此迫切需要能有效处理大量数据的机器学习算法。在BSGD算法(Budgeted Stochastic Gradient Descent)被提出以前，已经有许多算法可以处理大规模数据，但是其中大部分都属于线性分类器。针对大规模数据的带核的SVM算法比较少，这部分算法包括SimpleSVM、LASVM等等，它们存在的一个问题就是没有限制模型的大小，并且往往时间空间的开销是训练数据二次方，这些就限制了以上算法不能应用于比较大的数据集。
	
	一般随机梯度下降算法若想引入核技巧，则要保留下在训练过程中所有被分类错误的样本，这些样本一定是支持向量(SV)。随着训练的进行，这些样本的数量可能非常多，因此必然会带来巨大的时间与空间开销。为了缓解这一问题，研究者们提出了BSGD算法。BSGD算法属于一种随机梯度下降算法，该算法致力于解决普通的在线SVM算法引入核带来的性能问题，可以分类非线性数据。大体来说，算法通过一些策略来控制支持向量的数量，来降低更新分类器参数的时间空间开销，但是即便如此，该算法的性能仍然不令人满意。
	
	在开始介绍BSGD算法之前，我们先回顾一下朴素的梯度下降法求解SVM算法及其核技巧：
	带软间隔的SVM算法的优化问题如下：
	\begin{equation}
		\min P(\bm{\omega}) = \frac{\lambda}{2}\|\bm{\omega}\|^2 + \frac{1}{N}\sum_{t=1}^{N}l(\bm{\omega};(\bm{x}_t,y_t))
		\label{bsgdeq1}
	\end{equation}
	其中l为 hinge-loss\eqref{hingeloss}，$N$为训练集大小。
	
	随机梯度下降法是一个迭代过程，随机取$\bm{\omega}_1$，作为初始条件，此后在第$t$轮，$\bm{\omega}_t$按照如下规则更新：
	\begin{equation}
		\bm{\omega}_{t+1} = \bm{\omega}_t-\eta_t\nabla_t
		\label{bsgdeq2}
	\end{equation}
	其中，$\nabla_t$是第$t$轮的即时损失函数$P_t(\bm{\omega})=\frac{\lambda}{2}\|\bm{\omega}\|^2+l(\bm{\omega};(\bm{x}_t,y_t))$在$\bm{\omega}_t$处的梯度；$\eta_t$是第t轮的学习率。这样，\eqref{bsgdeq2}可重写为：
	\begin{align}
		\begin{split}
			\bm{\omega}_{t+1} &= (1-\lambda\eta_t)\bm{\omega}_t+\beta_t\bm{x}_t\\
			\beta_t &= 
			\begin{cases}
				\eta_ty_t,& \text{if }y_t\bm{\omega}_t\bm{x}_t<1\\
				0, & \text{otherwise}
			\end{cases}
		\end{split}
		\label{bsgdeq3}
	\end{align}
	
	以上就是使用梯度下降法求解SVM，最终得到的是一个线性模型。那么针对线性不可分的数据，一般是使用核技巧。具体来说，通过函数$\Phi(\bm{x})$把样本$\bm{x}$映射到高维特征空间，这样可以使在低维空间下线性不可分的数据变得线性可分。通过迭代消掉原SVM解\eqref{bsgdeq3}右侧的$\bm{\omega}_t$，并用$\Phi(\bm{x})$替换$\bm{x}$，即得到带核的SVM的解：
	\begin{align}
		\begin{split}
			\bm{\omega}_t &= \sum_{j=1}^{t}\alpha_j\Phi(\bm{x}_j)\\
			\alpha_j &=\beta_j\prod_{k=j+1}^{t}(1-\eta_k\lambda)\\
			\beta_j &= 
			\begin{cases}
				\eta_jy_j, & \text{if }y_j(\bm{\omega}_j\bm{\Phi(\bm{x}_j)})<1\\
				0, &\text{otherwise}
			\end{cases}
		\end{split}
		\label{bsgdsol1}
	\end{align}
	注意到，在第$t$轮若样本的间隔大于1，则有$\beta_t=\alpha_t=0$，那么该样本就不影响\eqref{bsgdsol1}对$\bm{\omega}_t$的值，否则，该样本分类错误，并会影响$\bm{\omega}_t$的值。因此，若样本在训练过程中被分类错误，则我们称之为``支持向量"。
	
	看似解决了线性不可分的问题，但是还没有，因为我们不知道函数$\bm{\Phi(\cdot)}$如何定义，为避开这个问题，常常用支持向量集与核函数$k(\cdot,\cdot)$隐式表达$\bm{\Phi(\cdot)}$与$\bm{\omega}$。因为$\bm{\Phi(\cdot)}$常常成对出现，所以这是可行的。在这篇文章中我们使用高斯核。
	
	为了使支持向量的数量保持固定，需要设定一个``预算"，用$B$表示，预算的大小决定着算法的时间和空间开销，因此不能过大，而预算过小则会影响算法的准确性。当新来的样例是一个支持向量时，若此时支持向量的数量已经达到预算，则按照一定的策略消除一个已经保存的支持向量，然后把当前的支持向量添加进来。在这篇文章中，我们随机选择一个旧的支持向量，并用新的替换它。在实际实现中，为简便起见，我们把训练集中前$B$个样本作为支持向量，此后每遇到一个支持向量，便随机替换掉一个已经保存的。
	
	若BSGD的迭代次数取$N$次，那么就可以看作是一种one-pass算法。
%==========6000==============

\section{Pegasos算法}\label{pegasos}%600
	Pegasos(Primal Estimated sub-GrAdient SOlver for SVM)算法是一种随机梯度下降方法，用来解决SVM问题。它不属于在线学习算法，但是具有在线学习算法的优秀性能，同时也能收敛到离线SVM的解。同时也可以方便地引入核技巧来处理非线性可分的数据。下面我们主要介绍线性的Pegasos算法。
	
	Pegasos使用类似随机梯度下降的方法求解\eqref{bsgdeq1}，该算法迭代$T$次，同时引入一个额外的参数$k$，它决定了算法每次迭代使用多少样本。可以看到，若$k$等于训练集样本数量$N$，则算法变成一般的梯度下降法；若$k$等于1，则算法变成一般的随机梯度下降法，并且若$k=1$且$T=N$，则就可以看作是one-pass算法。
	
	具体来说，在第$t$次迭代时，算法随机取大小为$k$的集合$A_t\subseteq S$，$S$为训练集，大小为$m$。然后用下面的优化问题替换原SVM的目标函数\eqref{bsgdeq1}：
	\begin{equation}
		\min P(\bm{\omega};A_t) = \frac{\lambda}{2}\|\bm{\omega}|^2+\frac{1}{k}\sum_{(\bm{x},y)\in A_t}l(\bm{\omega};(\bm{x},y))
		\label{pegeq1}
	\end{equation}
	其中函数$l(\bm{\omega};(\bm{x},y))$仍然是hinge-loss，定义由\eqref{hingeloss}给出。直观来看，这个方程可以看作是优化问题\eqref{bsgdeq1}的近似，因为\eqref{pegeq1}只选择了训练集的一部分点，而\eqref{bsgdeq1}针对的是整个训练集。也就是说，Pegasos每次迭代都是求\eqref{bsgdeq1}近似解的过程。同时，式\eqref{pegeq1}右侧也是第$t$次迭代的``即时损失"。

	有了上面给出的即时损失，我们需要求第$t$次迭代时，损失函数在$\bm{\omega}_t$处的梯度$\nabla_t$。对$\bm{\omega}$求偏导，得：
	\begin{equation}
		\nabla_t = \lambda\bm{\omega}_t-\frac{1}{|A_t|}\sum_{(\bm{x},y)\in A_t^+}y\bm{x}
	\end{equation}
	其中，$A_t^+$是那些hinge-loss不为0的样本的集合。
	
	那么对$\bm{\omega}$的迭代更新公式可写为：
	\begin{align}
		\bm{\omega}_{t+1}&=\bm{\omega}_t-\eta_t\nabla_t	\\
						 &=(1-\eta_t\lambda)\bm{\omega}_t+\frac{\eta_t}{k}\sum_{(\bm{x},y)\in A_t^+}y\bm{x}
	\end{align}
	其中，学习率$\eta_t$取$\frac{1}{\lambda t}$，这是为了保证算法的收敛时间为$\hat{\bm{O}}(\frac{d}{\lambda\epsilon})$，$d$是数据中不为0的特征的数量，$\epsilon$是与精度有关的常数。
	
\section{实验}\label{expe}%1626
	\subsection{数据集}
		我们一共在5个数据集上进行了测试，分别是a7，w7a，SVMGUIDE1，ijcnn1，CBCL Face(cbcl)\footnote{\url{http://cbcl.mit.edu/software-datasets/FaceData2.html}}，前四个可以在LibSVM的网站上\footnote{\url{www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/}}下载到。这些都是二分类的数据集，详细情况见表\ref{table1}。
			
		有一些数据集的正例与反例不是随机排列，正例与反例之间界限明显，这样的数据如果直接使用，则不能训练出正确的模型，对于这类数据集，我们把样本的顺序重新随机排列，然后保存文件；另外为了准确和方便，统一把样本特征缩放到$[0,1]$，类别标签取$\{-1,+1\}$
		\begin{table}[htp]
			\centering
			\begin{tabular}{cccccc}
			\hline
			\multirow{2}{*}{Dataset}&\multicolumn{2}{c}{training}&\multicolumn{2}{c}{test}&\multirow{2}{*}{feature}\\ \cline{2-5}
			&positive&negative&positive&negative&\\ \hline
			svmguide1&2000&1089&2000&2000&4	\\
			cbcl&2429&4548&472&23573&361	\\
			ijcnn1&4853&45137&8712&82989&22 \\
			a7a&5506&17190&3923&12538&123	\\
			w7a&740&23953&739&24318&300		\\
			\hline
			\end{tabular}
			\caption{本实验使用的数据集及描述}\label{table1}
		\end{table}
	\subsection{各算法的参数设置}
		在算法的参数设置方面，文献\cite{1}中介绍了大部分参数的值，我们参考这篇文章中的一些取值，其余一些没有被提到的参数，我们通过多次尝试或者经验取一个比较合适的值。具体来说，对于PA算法，正则项系数$C$取$\{10^{-4},10^{-3},\dots,10^4\}$；对于CW算法，置信度$\eta$取${0.7,0.75,\dots,0.95}$；对于SCW算法，结合CW算法，置信度$\eta$直接取0.95，因为更低的置信度不会有更准确的分类结果，而正则项系数$C$同样取$C$取$\{10^{-4},10^{-3},\dots,10^4\}$；对于LOL算法，正则项系数$C$取1，聚类中心点个数$k$取60，$\lambda$取1；对于BSGD算法，支持向量的预算大小取$B=500$，学习率$\eta_t$取$\frac{1}{\lambda t}$，学习率的参数$\lambda$取$\{10^{-4},10^{-3},\dots,10^3\}$，迭代次数为$N$次\footnote{确切地说是$N-B$次，因为初始的$B$个样本不迭代}，$N$为训练集大小；对于Pegsos算法，学习率$\eta_t$取$\frac{1}{\lambda t}$，学习率的参数$\lambda$取$\{10^{-5},10^{-4},\dots,10^5\}$，每次迭代抽取的样本数量$k$取50，迭代次数取$N$次，$N$为训练集大小.
	\subsection{算法评估方法}
		从表\ref{table1}中可以发现，除svmguide1之外的数据集，其正例数量与反例数量存在严重的不平衡问题，所以如果训练样本中某一类别的样本过少，那在进行分类的时候可能有欠拟合的问题，相应地对于剩余的数量过多的那一类样本，则有可能出现过拟合的问题，这就会导致训练出来的模型容易走向一个极端，即总是输出正例或总是输出反例，这样的模型正确分类的结果可以很高，但是意义并不大，因此若只看精度就显得不太科学，因此我们计算了各算法使用不同的参数在指定数据集上的真正例率、真反例率、伪正例率与伪反例率，保留那些真正例率与真反例率都高于30\%的计算结果（若无符合要求的则随机选择一个），然后再从这些结果中选择精度最高的。这样就不至于引用那些精度很高而没有意义的分类结果。
	
	\subsection{实验结果}
		我们按照数据集对各个算法的结果进行分组，使用前文的策略，每个算法在一个数据集上只保留一个比较优的计算结果，并在图上直观地表示出来，最终的结果如图\ref{figresult}所示，横轴分别表示真正例率（TP），假正例率（FP），假反例率（FN），真反例率（TN）和精度（P）。附录\ref{apnd}中给出了部分从\cite{1}中摘录下来的前人的实验参考错误率。
		\begin{figure}[htbp] 
			\centering
			\includegraphics[width=350pt]{result4.bmp}
			\caption{各算法在不同数据集上真正例、伪反例、伪正例、真反例与精度的比较结果}\label{figresult} 
		\end{figure}
		从图\ref{figresult}中可以看到，所有算法在数据集svmguide1上的结果都很好且十分相似，因此参考意义不大。而其余的数据集由于测试集中，反例的数量都多于正例，因此从大体来说，各算法在这些数据集上，对反例的分类结果都很准确，而对正例的分类结果就不太准确，造成这个问题的原因是多方面的，一方面算法固有的问题，另一方面数据集类别不平衡的问题，此外，我们在实验过程中，为方便起见，对于某个算法，并没有过多的尝试非常多的参数，这在一定程度上也影响着精度。
				
		在细节上，可以发现在数据集a7a上，PA、LOL、BSGD、Pegasos算法表现较好，而CW算法最差，SCW稍好于CW算法；在w7a上，各算法对反例的识别率相近，而对正例的识别，SCW、BSGD算法明显不足，Pegasos稍好，PA、LOL的分类结果最好；在cbcl上，各算法表现相近，其中BSGD、LOL算法对正例反例的识别率都比较高，而其他算法由于是线性分类器，精度稍差；在ijcnn1上，PA、LOL、BSGD算法对正反例的识别较高。另外值得一提的是，由于使用软间隔，SCW算法在各数据集上的表现都略优于CW算法。
		
		在性能上，由于BSGD算法使用了核技巧，CW、SCW算法引入了高斯分布，因此在求解优化问题上都需要大量的计算，所以性能上较其他三种算法差一些。对于ijcnn1数据集，这三种算法需要数分钟至十余分钟可以得到结果，而剩余三种算法可以在数秒之内计算完毕。
		\begin{table}
			\centering
			\begin{tabular}{ccccc}
				\hline
						&问题设置	&模型				&适用范围		&速度\\
				\hline	
				PA		&one-pass	&线性模型			&含噪声线性可分	&快 \\
				CW		&one-pass	&线性模型			&无噪声线性可分	&较慢\\
				SCW		&one-pass	&线性模型			&含噪声线性可分	&较慢\\
				LOL		&one-pass	&组合线性模型		&非线性			&快\\
				BSGD	&online		&带预算的核模型		&非线性			&非常慢\\
				Pegasos	&离线		&线性模型，可引入核	&线性/非线性	&快\\
				\hline
			\end{tabular}
			\caption{各算法的特性一览}
			\label{tab2}
		\end{table}
		最后，我们从多方面，对以上算法进行总结，如表\ref{tab2}所示：
\section{总结与展望}\label{con}%166
	从实验结果来看，PA、LOL、Pegasos算法的表现都比较好，CW与SCW算法表现较差；BSGD与LOL算法在处理非线性数据的时候有比较好的表现，而LOL兼顾性能与精度。因此可以得出结论，若已知数据是线性数据，则可选PA或Pegasos；若为非线性数据，同时要求高性能，则最好选用LOL，若对性能无特别要求，则可选用BSGD算法。
\nocite{8}
\appendix
\section{各算法的参考错误率}\label{apnd}
	\begin{table}[htp]
		\centering
		\begin{tabular}{cccc}
			\hline
			Method 	& SVMGUIDE1 			& CBCL 					& IJCNN1 				\\ \hline
			PA 		& $30.35\% \pm 0.107$ 	& $7.12\%  \pm 0.059$ 	& $34.98\% \pm 0.038$	\\
			Pegasos & $37.49\% \pm 0.126$ 	& $20.84\% \pm 0.182$ 	& $25.48\% \pm 0.068$	\\
			CW 		& $50.09\% \pm 0.243$ 	& $3.64\%  \pm 0.003$	& $46.41\% \pm 0.028$	\\
			SCW 	& $21.42\% \pm 0.010$	& $3.20\%  \pm 0.001$	& $46.96\% \pm 0.079$	\\
			BSGD 	& $5.73\%  \pm 0.009$ 	& $2.14\%  \pm 0.004$ 	& $4.36\%  \pm 0.000$	\\
			LOL 	& $5.26\%  \pm 0.014$ 	& $3.68\%  \pm 0.014$ 	& $3.15\%  \pm 0.006$	\\\hline
		\end{tabular}
		\caption{不同算法在部分数据集上的错误率}
	\end{table}
\bibliography{GraduationRefs}
\end{document}
